In the operation of a computer, software programs that are running on the computer require access to the computer's main memory, e.g., RAM, in order to carry out their operations. To this end, therefore, each program is allocated a range of memory addresses, which are available for use by that program. This range of allocated addresses is sometimes referred to as the program's address space. In actual practice, a program may only use a fraction of its allocated addresses at any given time. Consequently, if the allocated address space corresponds to actual physical space within the main memory, a large portion of the memory will not be used.
While this situation may be acceptable if only one program is running on the computer, it can present significant limitations if multiple programs are to be run, for example in a multi-tasking environment. More particularly, once address space is allocated to a particular program, it cannot be accessed by other programs, even if it is not being currently used, because it must always be available for use by the program to which it has been allocated. As a result, once all available memory has been allocated, additional programs cannot be run until some memory space is freed up, for example by closing a program.
To alleviate this situation, virtual memory technology has been developed. In this technology, the addresses that are assigned for use by individual programs are distinct from the actual physical addresses of the main memory. The addresses which are allocated to the programs are often referred to as "logical" or "virtual" or "effective" addresses, to distinguish them from the "physical" addresses of the main memory. Whenever a program requires access to memory, it makes a call to a logical address within its assigned address space. A memory manager associates this logical address with a physical address in the main memory, where the information called for by the program is actually stored. The identification of each physical address that corresponds to a logical address is commonly stored in a data structure known as a page table. This term is derived from the practice of dividing the memory into individually addressable blocks known as "pages".
Through the use of virtual memory, the available physical memory can be utilized more effectively. More particularly, physical addresses only need to be assigned to those logical addresses which are currently active. If a program is not using a portion of its assigned address space, no physical addresses need be associated with these unused logical addresses. By marking pages of data as temporarily inaccessible, the associated physical page can be copied to secondary storage and reassigned to map some other virtual page. As a result, a larger portion of the main memory is available for use by other programs. Each program can continue to operate as if it has a large contiguous address space available to it, however.
In many instances, two or more logical addresses may be mapped to the same locations in the physical memory. For example, two or more applications might share a common data file. Each application uses a different logical address to access the file. In this situation, the page table contains multiple references to the same physical address.
Since available physical addresses are mapped to logical addresses as needed, adjacent logical addresses are typically mapped to widely separated portions of physical memory, and vice versa. Furthermore, during operation the physical addresses are constantly being remapped as different operations are carried out. As a result, there is not necessarily a direct relationship between logical and physical addresses.
When an action occurs which removes the need for further memory accesses, e.g. an application program or a file is closed, it is no longer necessary to assign address space to that entity. Upon the occurrence of such an action, therefore, a command is sent to the memory manager to delete an area, or range of addresses, assigned to the file. At this point, however, the physical memory still has an entry or address mapped in the page table, which is therefore not free for other uses.
In order to free the addresses for further use, their corresponding entries must be removed from the page table. In some types of page tables, contiguous logical addresses are mapped to contiguous page table entries. In these types of page tables, when an address area is deleted, all of the page table entries associated with that area can be readily identified and removed from the table.
In other types of architectures, however, there is not such a direct relationship between logical addresses and page table entries. For example, in some architectures the physical address of the page table entry is determined by means of a hashing function. In this approach, the page table entry might be determined through a logical combination of different components of an address, for example in accordance with a prescribed function, rather than a straight index using one or more components of the address. As a result, page table entries which map adjacent logical addresses could be widely separated in the table. There is no fixed relationship between the locations of page table entries for adjacent logical addresses.
Consequently, when a file is closed, or portions of memory are otherwise rendered inactive, there is no simple, effective way to locate all page table entries that might be associated with the inactive addresses. Since the page table entries for a file could be scattered throughout the table, it may be necessary to check every entry in the page table, i.e. to scan the table. Alternatively, it is possible to compute all possible page table entries for the given range of inactive addresses, using the hashing function, and check each such entry. During the time that the scanning of the page table is being carried out to identify inactive entries, software programs might need to be temporarily halted. For computers having relatively large amounts of address space, and a large number of entries in their page tables, the time required to scan all of the entries in the page table can be considerable. If a complete scan of the page table is carried out at once, delays in the running of the programs can result. In addition, a complete scan of the page table may be too expensive an operation, in terms of operating efficiency, to carry out every time a range of addresses is inactivated.
Accordingly, it is desirable to provide a method for efficiently allocating and deallocating large amounts of address space in a virtual memory system that does not require excessive processing time and therefore does not result in unacceptable delays in the operation of a computer.